//无重复字符串的排列组合。编写一种方法，计算某字符串的所有排列组合，字符串每个字符均不相同。 
//
// 示例 1： 
//
// 
// 输入：S = "qwe"
// 输出：["qwe", "qew", "wqe", "weq", "ewq", "eqw"]
// 
//
// 示例 2： 
//
// 
// 输入：S = "ab"
// 输出：["ab", "ba"]
// 
//
// 提示： 
//
// 
// 字符都是英文字母。 
// 字符串长度在[1, 9]之间。 
// 
//
// Related Topics 字符串 回溯 👍 98 👎 0


package LeetCode.editor.cn;

import java.util.ArrayList;
import java.util.List;

/**
 * @author ldltd
 * @date 2025-08-30 22:56:42
 * @description 面试题 08.07.无重复字符串的排列组合
 */
public class PermutationILcci{
	 public static void main(String[] args) {
	 	 //测试代码
	 	 PermutationILcci fun=new PermutationILcci();
	 	 Solution solution = fun.new Solution();

	 }
	 
//力扣代码
//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    public String[] permutation(String S) {
		char[] charArray = S.toCharArray();
		boolean[] used=new boolean[charArray.length];
		List<String> res=new ArrayList<>();
		backtrack(res,new StringBuilder(),charArray,used);
		return res.toArray(new String[0]);
	}
	public void backtrack(List<String> res,StringBuilder tempList,char[] charArray,boolean[] used) {
		if (tempList.length() == charArray.length) {
			res.add(tempList.toString());
		} else {
			for (int i = 0; i < charArray.length; i++) {
				if (used[i]) continue;
				used[i] = true;
				tempList.append(charArray[i]);
				backtrack(res, tempList, charArray, used);
				used[i] = false;
				tempList.deleteCharAt(tempList.length() - 1);
			}
		}
	}
}
//leetcode submit region end(Prohibit modification and deletion)

}
